package com.acwing;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * 多重背包单调队列优化
 * 原始方程:   dp[j] = max( dp[j - k*w] + k*v )  （k的范围：0 ≤ k ≤ s）
 * dp[r + t*w] = max( dp[r + (t - k)*w] + k*v )
 * 令k' = t - k, 分离常量与变量，构造 “增量价值”:
 * dp[r + t*w] = max( dp[r + k'*w] - k'*v ) + t*v
 * val(k') = dp[r + k'*w] - k'*v, 维护 val(k') 的单调队列:
 * dp[r + t*w] = max( val(k') ) + t*v  （k'的范围：t - s ≤ k' ≤ t）
 * 变形后的方程有两个关键特点，刚好适配单调队列：
 * max 的范围是 “滑动窗口”：k'的范围是[t-s, t]，随着t增大（组内容量递增），窗口向右滑动（窗口大小固定为s+1）；
 * 每次只需取窗口最大值：单调队列的核心作用就是 “维护滑动窗口内的最大值”，让每次取 max 的时间从O(s)降至O(1)。
 * 队列维护的具体操作（对应代码）：
 * 入队前：移除队列中val(k') ≤ 当前val(t)的元素（保证队列单调递减，队首是最大值）；
 * 入队后：移除队列中k' < t - s的元素（保证窗口不超出 “最多取s个” 的限制）；
 * 状态转移：队首元素就是最优k'，代入dp[r + t*w] = val(队首k') + t*v，即完成计算
 */


/**
 * 多重背包单调队列优化（最终稳定版）
 * 时间复杂度：O(n*cap)，空间复杂度：O(cap)
 * 适配场景：物品种类多、背包容量大的大规模多重背包问题
 */


public class No6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cap = sc.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        int[] s = new int[n];

        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }
        sc.close();

        System.out.println(maxValue(n, cap, w, v, s));
    }

    private static int maxValue(int n, int cap, int[] w, int[] v, int[] s) {
        int[] dp = new int[cap + 1];

        for (int i = 0; i < n; i++) {
            int weight = w[i];
            int value = v[i];
            int count = s[i];

            if (weight > cap) continue;
            count = Math.min(count, cap / weight);

            for (int r = 0; r < weight; r++) {
                Deque<Integer> deque = new ArrayDeque<>();
                int maxT = (cap - r) / weight;

                // 正向遍历t（0→maxT），这样窗口逻辑更清晰
                for (int t = 0; t <= maxT; t++) {
                    int currCap = r + t * weight;
                    int currInc = dp[currCap] - t * value;

                    // 维护队列递减性
                    while (!deque.isEmpty()) {
                        int lastT = deque.peekLast();
                        int lastInc = dp[r + lastT * weight] - lastT * value;
                        if (lastInc <= currInc) {
                            deque.pollLast();
                        } else {
                            break;
                        }
                    }
                    deque.offerLast(t);

                    // 维护窗口范围：移除超出左边界的元素 (t - count)
                    while (!deque.isEmpty() && deque.peekFirst() < t - count) {
                        deque.pollFirst();
                    }

                    // 状态转移
                    if (!deque.isEmpty()) {
                        int bestT = deque.peekFirst();
                        int bestValue = dp[r + bestT * weight] + (t - bestT) * value;
                        dp[currCap] = Math.max(dp[currCap], bestValue);
                    }
                }
            }
        }
        return dp[cap];
    }
}